//对 长 度 为 n 的 顺 序 表 L ， 编 写 一个 时 间 复 杂 度 为 0 (n ) 、 空 间 复 杂 度 为 Q ( 1 ) 的 算 法 ，
// 该 算 法删除顺序表中所有值为x，的数据元素
#include<iostream>
using namespace std;
#define MaxSize 50
#define ElemType int

struct List{
    ElemType data[MaxSize];
    int length;

    int InitList(List &L){
        L.length=0;
        return L.length;
    }

    int Length(List &L){
        return L.length;
    }

    bool ListInsert(List &L,int i,ElemType e){
        if(i<1||i>L.length+1){   //判断i的范围是否有效
            return false;
        }
        if(L.length>=MaxSize){   //当前存储空间已满，不能插入
            return false;
        }
        for (int j = L.length; j >= i; j--){ //将第i个元素及之后的元素后移
            L.data[j]=L.data[j-1];
        }
        L.data[i-1]=e;           //在第i个位置放入e
        L.length++;              //线性表长度加1
        return true;
        
    }
};

bool deleteX(List &l,ElemType x){
    //使用双指针
    int count=0;//l中值为x的元素个数
    int i=0,j=0;//i，j代表两个指针，值为l元素索引，初始都为0
    for (int i = 0; i < l.length; i++,j++)//每次循环i，j分别加1
    {
        while (j<l.length&&l.data[j]==x)//如果j指向的元素等于x，j++，只到j指向元素不等于x
        {
            j++;
            count++;//记录l中值为x的元素个数
        }
        if(j<l.length){
            l.data[i]=l.data[j];
        }        
    }
    l.length-=count;
    return true;
}

//标准答案
void deleteX2(List &l,ElemType x){
    //使用双指针
    int i=0,k=0;//k记录值等于x元素的个数
    while (i<l.length)
    {
        if(l.data[i]==x){
            k++;
        }else{
            l.data[i-k]=l.data[i];
        }
        i++;
    }
    l.length-=k;
}
//法2
void deleteX3(List &l,ElemType x){
    //使用双指针
    int i=0,k=0;//k记录值等于x元素的个数
    while (i<l.length)
    {
        if(l.data[i]!=x){
            l.data[k]=l.data[i];
            k++;
        }
        i++;
    }
    l.length=k;//顺序表的长度等于k
}

int main(){
    List l;
    l.InitList(l);
    l.ListInsert(l,1,1);
    l.ListInsert(l,1,2);
    l.ListInsert(l,1,2);
    l.ListInsert(l,1,3);
    l.ListInsert(l,1,4);
    l.ListInsert(l,1,2);
    cout<<l.data[0]<<","<<l.data[1]<<","<<l.data[2]<<","<<l.data[3]<<","<<l.data[4]<<","<<l.data[5]<<endl;
    // cout<<deleteX(l,2)<<endl;
    // deleteX2(l,2);
    deleteX3(l,2);
    cout<<l.data[0]<<","<<l.data[1]<<","<<l.data[2]<<","<<l.data[3]<<","<<l.data[4]<<","<<l.data[5]<<endl;
    return 0;
}
